{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-16T21:33:17.614180Z",
     "start_time": "2019-10-16T21:33:13.000006Z"
    },
    "execution": {
     "iopub.execute_input": "2021-12-30T08:22:35.420376Z",
     "iopub.status.busy": "2021-12-30T08:22:35.420095Z",
     "iopub.status.idle": "2021-12-30T08:22:36.396850Z",
     "shell.execute_reply": "2021-12-30T08:22:36.396302Z",
     "shell.execute_reply.started": "2021-12-30T08:22:35.420291Z"
    },
    "scrolled": true,
    "tags": []
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import random\n",
    "from itertools import combinations\n",
    "import joblib\n",
    "from tqdm.notebook import trange, tqdm\n",
    "from matplotlib import pyplot as plt\n",
    "import numba as nb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduce VCG Auction and implement it"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行What is VCG Auction? From Wiki https://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%93Groves_auction:\n",
    "\n",
    "考虑出售一组相同产品的拍卖。 投标人可以通过宣布他们愿意为收到 N 件产品支付的最高价格来参与拍卖。 每个买家可以申报多个投标，因为其每单位的支付意愿可能会因收到的单位总数而异。 投标人在任何时候都无法看到其他人的投标，因为它们是密封的（仅对拍卖系统可见）。 一旦所有出价都完成，拍卖就会结束。\n",
    "\n",
    "然后拍卖系统会考虑所有可能的出价组合，并保留使出价总和最大化的那个，条件是它不超过可用产品的总量，并且每个出价人最多可以出一个出价 使用。 成功投标的投标人会收到他们投标中指定的产品数量。 然而，他们作为交换支付的价格不是他们最初出价的金额，而只是他们的出价对其他出价者造成的边际损害（最多与他们最初的出价一样高）。\n",
    "\n",
    "这种对其他参与者造成的边际伤害（即每个中标的个人支付的最终价格）可以计算为：（排除考虑中的参与者的最佳投标组合的拍卖投标总和）-（还有哪些其他中标者 投标人在当前（最佳）投标组合中投标）。 如果第二个最佳投标组合的投标总和与最佳投标组合的投标总和相同，则买方支付的价格将与其最初的投标相同。 在所有其他情况下，买家支付的价格会更低。\n",
    "\n",
    "在拍卖结束时，总效用最大化，因为所有商品都归属于支付意愿最高的人。 如果代理人完全理性并且没有勾结，我们可以假设支付意愿已经被真实报告，因为每个参与者只会对其他投标人造成边际伤害，使得真实报告成为弱主导策略。 然而，这种类型的拍卖不会使卖方的收入最大化，除非第二最佳出价组合的出价总和等于最佳出价组合的出价总和。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-17T01:39:35.267148Z",
     "start_time": "2019-10-17T01:39:35.088558Z"
    },
    "execution": {
     "iopub.execute_input": "2021-12-30T08:22:36.398710Z",
     "iopub.status.busy": "2021-12-30T08:22:36.398353Z",
     "iopub.status.idle": "2021-12-30T08:22:36.411963Z",
     "shell.execute_reply": "2021-12-30T08:22:36.411360Z",
     "shell.execute_reply.started": "2021-12-30T08:22:36.398678Z"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class VCG_Auction_Process(object):\n",
    "    def __init__(self,value_mat_origin):\n",
    "        self.value_mat_origin=value_mat_origin\n",
    "        self.value_mat=self.value_mat_origin\n",
    "        self.allocation=self.value_mat.columns # For single-item condition 每个商品单独价格\n",
    "        self.best_price=0 #Initialization\n",
    "    \n",
    "    def who_win(self):  ### 一个一个bundle计算\n",
    "        '''\n",
    "        Pick up the winners for each item, if bids are the same, then a winner will be randomly picked\n",
    "        '''\n",
    "        self.winner_list=[] #Bidder index for each winner of the item\n",
    "        self.second_price_list=[]\n",
    "        winner_temp=[]\n",
    "        \n",
    "        for item_set in self.allocation:   ### 一个 bundle 可能有多个物品, 输入值是物品代号 [0, 1, 2, ...]\n",
    "            item_represent=item_set[0] #Because all other items in the set share the same value,一个bundle只计算一个价格\n",
    "            ### 在一个 bundle 中计算, 得到 每个 bundle 中出价最高的 player, 可以有多个\n",
    "            winner_temp.append(np.where(self.value_mat[item_represent]==np.max(self.value_mat[item_represent]))[0])\n",
    "        \n",
    "        for item_set_index,winner in enumerate(winner_temp):\n",
    "            item_set=self.allocation[item_set_index] ### 返回index # The item set like [0,1]\n",
    "            item_represent=item_set[0]# Representation ### 一个bundle,一个价格\n",
    "            if len(winner)>1: ### 多人最高价,随机选择\n",
    "                #print(\"Item set {:} has multiple winner: {:}\".format(item_set,winner))\n",
    "                random.seed(10)\n",
    "                self.winner_list.append(random.choice(winner))\n",
    "                second_price=sorted(self.value_mat[item_represent])[-2]\n",
    "                # Add the payment of each winner, pay your value if the \"same\" occur\n",
    "                self.second_price_list.append(second_price) \n",
    "            else:\n",
    "                self.winner_list.append(winner[0])\n",
    "                second_price=sorted(self.value_mat[item_represent])[-2]\n",
    "                self.second_price_list.append(second_price)\n",
    "        #print(self.value_mat)\n",
    "        #print(self.winner_list)\n",
    "        return self.winner_list,self.second_price_list\n",
    "    \n",
    "    def winner_price(self):   ### VCG机制 (Winner不参加强况下的social welfare - Winner参加时其他player的welfare)\n",
    "        ### VCG机制在在单物品情况下会退化为二价拍卖\n",
    "        '''\n",
    "        Calculate the price that the winner does to other agents and the mechanism will charge the price for each winner\n",
    "        \n",
    "        Make sure function who_win is run in advance\n",
    "        '''\n",
    "        self.welfare_list=[] # List for the welfare contributed by the winner. the sum of this list is the social welfare\n",
    "        self.price_list=[] # List for the price that the winner charged, for losers they don't pay\n",
    "        value_winner_list=[]\n",
    "        value_without_winner_list=[]\n",
    "        # Get the value list of winner\n",
    "        # With the winners\n",
    "        for item_set_index,winner in enumerate(self.winner_list):\n",
    "            item_set=self.allocation[item_set_index] # The item set like [0,1]\n",
    "            item_represent=item_set[0]# Representation\n",
    "            value_winner_list.append(self.value_mat[item_represent].iloc[winner])\n",
    "        self.welfare_list=value_winner_list\n",
    "        # Without the winners\n",
    "        value_without_winner_list=self.second_price_list\n",
    "        # Contribution of the winner\n",
    "        \n",
    "        ctrib_list=list(map(lambda x: x[0]-x[1],zip(value_winner_list,value_without_winner_list)))\n",
    "        # Price of the winner charged by the mechanism\n",
    "        self.price_list=list(map(lambda x: x[0]-x[1],zip(value_winner_list,ctrib_list)))\n",
    "        return self.price_list,self.welfare_list\n",
    "    def allocate_items(self,allocation):\n",
    "        '''\n",
    "        Allocate different sets of items\n",
    "        '''\n",
    "        self.allocation=allocation# Consider a finxed allocation case\n",
    "        self.update_value_mat()\n",
    "    \n",
    "    def update_value_mat(self):\n",
    "        '''\n",
    "        Update the value of bidders for item sets as the value of item sets are the maximum value inside\n",
    "        '''\n",
    "        self.value_mat=self.value_mat_origin.copy()\n",
    "        for set_index,item_set in enumerate(self.allocation):\n",
    "            for bidder,value in self.value_mat.iterrows():\n",
    "                self.value_mat.iloc[bidder][item_set]=np.max(self.value_mat.iloc[bidder][item_set])\n",
    "                \n",
    "    def find_best_allocation_price(self,current_price):\n",
    "        if current_price>=self.best_price:\n",
    "            self.best_allocation=self.allocation # Initialization\n",
    "            self.best_price=current_price\n",
    "        \n",
    "    def begin(self,possible_allocations):\n",
    "        f=open('allocation_price.txt','w+')\n",
    "        for allocation in tqdm(possible_allocations): #Define your possible_allocations here:   \n",
    "            ### 拍卖的商品是固定的,但是可能会有捆绑,需要确定所有可行的拍卖分配\n",
    "            ### 一个一个bundle计算\n",
    "            self.allocate_items(allocation)   ### 传入一个可行的商品分配\n",
    "            self.who_win()      \n",
    "            self.winner_price()\n",
    "            self.find_best_allocation_price(np.sum(np.sum(self.price_list)))\n",
    "            f.write('For Allocation: {:} Pirce charged by mechanism {:} and total {:}\\n'.format(\n",
    "            self.allocation,self.price_list,np.sum(self.price_list)))\n",
    "        f.close()\n",
    "        print('Best allocation: {:} and the mechanism charges {:}'.format(self.best_allocation,self.best_price))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You only need to define your possible allocation of items for iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Enumerate all the allocation to find the best allocation and price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-12T14:33:06.684187Z",
     "start_time": "2019-10-12T14:33:06.654269Z"
    },
    "execution": {
     "iopub.execute_input": "2021-12-30T08:22:36.413373Z",
     "iopub.status.busy": "2021-12-30T08:22:36.412978Z",
     "iopub.status.idle": "2021-12-30T08:22:36.427965Z",
     "shell.execute_reply": "2021-12-30T08:22:36.427518Z",
     "shell.execute_reply.started": "2021-12-30T08:22:36.413341Z"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "      <th>7</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>26</td>\n",
       "      <td>8</td>\n",
       "      <td>59</td>\n",
       "      <td>5</td>\n",
       "      <td>42</td>\n",
       "      <td>17</td>\n",
       "      <td>6</td>\n",
       "      <td>34</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>11</td>\n",
       "      <td>18</td>\n",
       "      <td>53</td>\n",
       "      <td>9</td>\n",
       "      <td>40</td>\n",
       "      <td>22</td>\n",
       "      <td>17</td>\n",
       "      <td>35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>19</td>\n",
       "      <td>25</td>\n",
       "      <td>50</td>\n",
       "      <td>24</td>\n",
       "      <td>49</td>\n",
       "      <td>23</td>\n",
       "      <td>21</td>\n",
       "      <td>31</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "      <td>52</td>\n",
       "      <td>3</td>\n",
       "      <td>45</td>\n",
       "      <td>14</td>\n",
       "      <td>21</td>\n",
       "      <td>38</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>23</td>\n",
       "      <td>54</td>\n",
       "      <td>28</td>\n",
       "      <td>47</td>\n",
       "      <td>17</td>\n",
       "      <td>14</td>\n",
       "      <td>33</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>22</td>\n",
       "      <td>27</td>\n",
       "      <td>57</td>\n",
       "      <td>27</td>\n",
       "      <td>43</td>\n",
       "      <td>19</td>\n",
       "      <td>23</td>\n",
       "      <td>36</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>21</td>\n",
       "      <td>19</td>\n",
       "      <td>55</td>\n",
       "      <td>28</td>\n",
       "      <td>46</td>\n",
       "      <td>16</td>\n",
       "      <td>5</td>\n",
       "      <td>32</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>20</td>\n",
       "      <td>12</td>\n",
       "      <td>56</td>\n",
       "      <td>18</td>\n",
       "      <td>41</td>\n",
       "      <td>16</td>\n",
       "      <td>10</td>\n",
       "      <td>39</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>2</td>\n",
       "      <td>4</td>\n",
       "      <td>58</td>\n",
       "      <td>28</td>\n",
       "      <td>48</td>\n",
       "      <td>26</td>\n",
       "      <td>15</td>\n",
       "      <td>30</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>20</td>\n",
       "      <td>9</td>\n",
       "      <td>51</td>\n",
       "      <td>10</td>\n",
       "      <td>44</td>\n",
       "      <td>20</td>\n",
       "      <td>6</td>\n",
       "      <td>37</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    0   1   2   3   4   5   6   7\n",
       "0  26   8  59   5  42  17   6  34\n",
       "1  11  18  53   9  40  22  17  35\n",
       "2  19  25  50  24  49  23  21  31\n",
       "3   2   3  52   3  45  14  21  38\n",
       "4   1  23  54  28  47  17  14  33\n",
       "5  22  27  57  27  43  19  23  36\n",
       "6  21  19  55  28  46  16   5  32\n",
       "7  20  12  56  18  41  16  10  39\n",
       "8   2   4  58  28  48  26  15  30\n",
       "9  20   9  51  10  44  20   6  37"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# variables\n",
    "### 输入 player 对 每个 商品的报价, 无论分配\n",
    "value_mat_origin=pd.read_table('Assignment#2-Q8-values.txt',delimiter=' ',header=None)\n",
    "value_mat_origin=value_mat_origin.drop([8],axis=1)\n",
    "value_mat_origin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Generate all possible allocation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[[0, 1, 2, 3, 4, 5, 6, 7]]]\n"
     ]
    }
   ],
   "source": [
    "### 输入 可能的 物品 buddle 分类 \n",
    "possible_allocations = joblib.load('possible_allocations_8.asv')\n",
    "print(possible_allocations)\n",
    "possible_allocations = [[[0]], [[1]], [[2]], [[3]], [[4]], [[5]], [[6]], [[7]]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Run VCG Auction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-17T01:39:43.715875Z",
     "start_time": "2019-10-17T01:39:39.904171Z"
    },
    "execution": {
     "iopub.status.idle": "2021-12-30T08:27:34.920660Z"
    }
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "fb8499a264884d1a8dab5ab56eb82e09",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "  0%|          | 0/8 [00:00<?, ?it/s]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[26] [4] [22]\n",
      "[27] [2] [25]\n",
      "[59] [1] [58]\n",
      "[28] [0] [28]\n",
      "[49] [1] [48]\n",
      "[26] [3] [23]\n",
      "[23] [2] [21]\n",
      "[39] [1] [38]\n",
      "Best allocation: [[2]] and the mechanism charges 58\n"
     ]
    }
   ],
   "source": [
    "vcg=VCG_Auction_Process(value_mat_origin)  ### 输入 bidder 支付价格\n",
    "vcg.begin(possible_allocations)   ### 输入分配矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 计算时间\n",
    "| possible_allocation | allocation_num | Exec_time | Except exec time |\n",
    "| :-----: | :----: | :----: |:----: |\n",
    "| possible_allocation_1 | 1 | 0sec | 0sec |\n",
    "| possible_allocation_2 | 5765760 | NULL | 46h |\n",
    "| possible_allocation_3 | 5651520 | NULL | 30h |\n",
    "| possible_allocation_4 | 70560 | 21min 20sec | 21min |\n",
    "| possible_allocation_5 | 1680 | 29sec | 30sec |\n",
    "| possible_allocation_6 | 112 | 1sec | 1sec |\n",
    "| possible_allocation_7 | 8 | 0sec | 0sec |\n",
    "| possible_allocation_8 | 1 | 0sec | 0sec |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [1, 8, 112, 1680, 70560, 5651520, 5765760]\n",
    "y = [0, 0, 1, 30, 21*60, 30*60*60, 46*60*60]\n",
    "\n",
    "plt.plot(x,y)\n",
    "\n",
    "from scipy.optimize import curve_fit\n",
    "\n",
    "def func(x, a, b):\n",
    "    return x**a + b\n",
    "\n",
    "popt, pcov = curve_fit(func, x, y)\n",
    "\n",
    "y2 = [func(i, popt[0],popt[1]) for i in x]\n",
    "plt.plot(x, y2,'r--')\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "interpreter": {
   "hash": "80297a49353e01fd30519dbbd85f9d444d6210a697f633f8361ee088cad82092"
  },
  "kernelspec": {
   "display_name": "paddleGPU:Python",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.10"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
